Antoine Mottet

Constraint satisfaction problems over finite structures

Recently, some extension was proposed by Barto, DeMeo, and Mottet, where constraint languages with relations and operations were considered. A similar dichotomy P vs. NP-complete result was obtained for constraints over a two-element set, but the problem for general finite sets remains wide open.

Goals

The goal of the internship is to develop the existing methods and prove complexity dichotomies for larger classes of constraint languages, in particular in the 3-element case. The tools that will be employed are mathematical in nature, leveraging the theory of universal algebras.

• Bachelor: read and write a report on [1] and [2]; compute an example of a structure with 3 elements that is not covered by the result in [2] and investigate the complexity of its CSP.
• Master: read [1] and [2], investigate a complexity dichotomy for the CSPs of all 3-element structures.

Another possible goal is to implement the algorithm described in Reference [2].

References

1. Constraint Satisfaction Problems over Finite Structures.
   Libor Barto, William DeMeo, Antoine Mottet.
2. Finite Algebras with Hom-Sets of Polynomial Size.
   Libor Barto, Antoine Mottet.

Promise Constraint Satisfaction

A promise CSP is parameterized by two structures $\mathbb A$ and $\mathbb B$ such that there exists a homomorphism from $\mathbb A$ to $\mathbb B$.
The PCSP of the pair $(\mathbb A,\mathbb B)$ takes as input a structure $\mathbb X$ and asks to distinguish between two cases:

• Yes: there exists a homomorphism $\mathbb X\to\mathbb A$
• No: there does not exist a homomorphism $\mathbb X\to\mathbb B$

Note that it cannot be the case that $\mathbb X$ satisfies both Yes and No; and we are promised that it satisfies at least one of them, hence the name. For example the PCSP of the pair $(\mathbb K_3,\mathbb K_{17})$ asks to determine whether a given graph is $3$-colorable, or not even $17$-colorable. The complexity of this problem is unknown! Therefore, no dichotomy like the Bulatov-Zhuk dichotomy is known for PCSPs.

The same algebraic tools used for traditional CSPs can be used for PCSPs, in particular a notion of polymorphism exists that characterize the complexity of the problems.

Goals

Depending on the level of the student, the goal can be one of the following:

• Read some recent articles and write a thesis about the state-of-the-art,
• Study the polymorphisms of templates of the form $(\mathbb C_{2n+1},\mathbb K_4)$ where $n\geq 1$ (the case $(\mathbb C_{2n+1},\mathbb K_3)$ is done in Reference [2]). For this, computer experiments can be performed and methods from machine learning can be used.

References

1. An invitation to promise constraint satisfaction.
   Andrei Krokhin, Jakub Opršal.
2. The complexity of 3-coloring $H$-colorable graphs.
   Andrei Krokhin, Jakub Opršal.

Oligomorphic matroids

A matroid is a combinatorial structure that captures two essential notions in mathematics: the concept of linear independence in vector spaces, and the concept of spanning forests in graphs. They enjoy many properties (for example, there exists a duality notion for matroids that allows to define a concept of dual for graphs that are not planar) and have found uses in several different areas of mathematics. Matroids were recently in the news, as June Huh received the Fields medal in 2022 for solving one of the long standing open problems in matroid theory. Most of the time, the matroids are considered to be finite, but it is possible to consider infinite matroids as well (see Reference [1]).

Goals

For this topic, we consider oligomorphic matroids: these are infinite matroids on which a permutation group acts and making the matroid behave essentially like a finite matroid. These matroids have never been studied in the literature, and the task is to start exploring the properties of these matroids and establish their basic theory.

References

1. Axioms for infinite matroids.
   Henning Bruhn, Reinhard Diestel, Matthias Kriesell, Rudi Pendavingh, Paul Wollan.

Infinite-domain constraint satisfaction

By allowing the domain of the constraint language of a CSP to have an infinite domain, the associated class of problems captures all decision problems! Looking for an extension of the Bulatov-Zhuk result to infinite-domain CSPs is therefore too ambitious in general, but one can restrict the class of constraint languages to so-called reducts of finitely bounded homogeneous structures. The Bodirsky-Pinsker conjecture states that this class of CSPs also admits a P/NP-complete dichotomy, where this time the border between tractable and intractable problems is conjectured to be characterized by algebraic and topological conditions. Recently, a new theory has been proposed by Mottet and Pinsker to approach this conjecture. This theory relies on a new tool, called smooth approximations, with which one could provide unified proofs of all known results involving the Bodirsky-Pinsker conjecture.

Goals

The goal of the internship is to develop the theory of smooth approximations to be able to overcome its current limitations. In particular, this internship will involve a mix of algorithmic, Ramsey theory, universal algebra, and model theory.

References

1. Smooth Approximations and CSPs over finitely bounded homogeneous structures.
   Antoine Mottet, Michael Pinsker.
2. Smooth Approximations and Relational Width Collapses.
   Antoine Mottet, Tomáš Nagy, Michael Pinsker, Michal Wrona.

Circuit complexity of constraint satisfaction problems

In the references, the circuit complexity of boolean CSPs is considered. The size and depth of (monotone or non-monotone) circuits solving a given CSP is investigated.

Goals

Generalize some of the results to CSPs over domains with more elements.

References

1. The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem
   Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer.
2. Constant-depth circuits vs. monotone circuits
   Bruno Cavalar, Igor Oliveira.

A topological version of Schaefer's theorem (solved)

Reference [1] looks at the topological complexity of the possible solution sets for instances of CSP($\mathbb A$), where $\mathbb A$ is a two-element structures.
With every solution set of an instance $I$, one can associate a cubical complex (like a simplicial complex but where faces are generalizations of squares and cubes).
A semi-algebraic set is a subset of $\mathbb R^d$ that is a union of sets defined by polynomial equalities and inequalities.
The authors prove that Pol($\mathbb A$) is the clone of projections iff for every compact semi-algebraic set $S$, there exists an instance of CSP($\mathbb A$) whose associated cubical complex is homeomorphic to $S$.

Goal

• Bachelor: read [1] and write a report on it with full proofs and prerequisites.
• Master: Generalize the methods from [1] to pp-interpretations, pp-constructions and show that similar results can be obtained for CSPs with more elements.

References

1. A topological version of Schaefer's theorem.
   Patrick Schnider, Simon Weber.

A minion of graphs (taken)

An $n$-marked graph is a graph $G=(V,E)$ such that $n$ of its vertices are labelled by the numbers $1$ to $n$. Given two $n$-marked graphs $G$ and $H$, one defines $G\oplus H$ to be the graph obtained by taking the disjoint union of the graphs and gluing the vertices according to their labels. If $G$ is $n$-marked and $\sigma\colon\{1,\dots,n\}\to\{1,\dots,m\}$, one can define $G^\sigma$ to be the $m$-marked graph obtained by gluing the vertices of $G$ according to $\sigma$; if some $i\in\{1,\dots,m\}$ is not in the image of $\sigma$, we simply introduce in $G^\sigma$ a vertex labelled $i$ that is not connected to any other vertex. This way, the set of finite marked graphs forms a minion (something behaving similarly to Pol($\mathbb A$)), whose elements of "arity" $n$ are the $n$-marked graphs.

A tree decomposition of a graph $G$ is a tree whose vertices are bags of vertices from $G$ and satisfying certain conditions. The width of the tree decomposition is the maximal size of a bag minus 1, and the treewidth of $G$, denoted by $tw(G)$, is the smallest width of a tree decomposition of $G$. The treewidth of $G$ measures how "tree-like" $G$ is: trees have treewidth 1, while the clique on $n$ vertices has treewidth $n-1$.

Fix a number $k$. For every $n\geq 1$, define an equivalence relation $\sim_n$ on $n$-marked graphs as follows: $\mathbb G\sim_n\mathbb G'$ iff for every $n$-marked graph $\mathbb H$, we have that $tw(G\oplus H)\leq k \Longleftrightarrow tw(G'\oplus H)\leq k$. The relation $\sim_n$ has finitely many equivalence classes, for all $n$.

Goals

Investigate the following questions:

• Is it true that if $G\sim_n H$, and $\sigma\colon\{1,\dots,n\}\to\{1,\dots,m\}$ is an arbitrary function, then $G^\sigma\sim_m H^\sigma$?
• If so, then one can define a minion whose elements of arity $n$ are the equivalence classes of $\sim_n$. Since $\sim_n$ has finitely many equivalence classes, this is a locally finite minion. Investigate the relationship between this minion and other minions known in the theory of PCSPs.